package alg;

/**
 * @author jarryxu
 * @version 1.0
 * @title SkipList.java
 * @package alg
 * @date 2023/9/28 14:17
 * @description
 */
public class SkipList<E> {
    /**
     maxLevel 索引最大高度
     currentLevel 当前索引高度
     head 跳表头节点，从head查起
     */
    private int maxLevel;
    private int currentLevel;
    private SkipNode<E> head;

    public SkipList(int maxLevel){
        this.maxLevel = maxLevel;
        head = new SkipNode(0,null,maxLevel);
    }

    public int getMaxLevel() {
        return maxLevel;
    }

    public int getCurrentLevel() {
        return currentLevel;
    }

    public SkipNode<E> getHead() {
        return head;
    }

    public static class SkipNode<E> {
        private int key;
        private E value;
        /**
         数组存储每层索引的下一个节点。比如下标0表示链表本身，
         下标1表示第一层索引，依次类推。
         */
        private SkipNode<E>[] next;

        public SkipNode( int key, E value, int length ){
            this.key = key;
            this.value = value;
            next = new SkipNode[length];
        }
    }

    public void insert( int key, E data ){
        SkipNode c = this.head;
        SkipNode[] update = new SkipNode[maxLevel];
        for( int i=currentLevel-1; i>=0; i--){
            while(c.next[i]!=null&&key>c.next[i].key){
                c=c.next[i];
            }
            if(c.key==key){
                c.value = data;
                return;
            }
            /**
             记录每一层的入口节点，如果要插入索引下面会用到
             */
            update[i] = c;
        }

        int randomLevel = getRandomLevel();
        SkipNode newNode = new SkipNode(key,data,randomLevel);

        if(randomLevel>currentLevel){
            for( int i=currentLevel; i<randomLevel; i++ ){
                update[i]=this.head;
            }
            currentLevel = randomLevel;
        }
        /**
         当前节点作为新索引节点，更新每一层的索引指向
         */
        for( int i=randomLevel-1; i>=0;i--){
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }

    public E search( int key ){
        SkipNode<E> c = this.head;
        for( int i = currentLevel-1; i>=0; i-- ){
            while(c.next[i]!=null&&key> c.next[i].key){
                c=c.next[i];
            }
            if(c.next[i]!=null&&c.next[i].key==key){
                return c.next[i].value;
            }
        }
        return null;
    }

    public void delete( int key ){

        SkipNode skipNode = this.head;
        SkipNode[] delete = new SkipNode[currentLevel];
        for( int i=currentLevel-1; i>=0; i-- ){
            while( skipNode.next[i]!=null&&skipNode.next[i].key<key){
                skipNode = skipNode.next[i];
            }
            delete[i]=skipNode;
        }
        if(delete[0].next[0]!=null&&delete[0].next[0].key==key){
            SkipNode deleteNode = delete[0].next[0];

            for( int i=0; i<currentLevel; i++ ){
                if(delete[i].next[i]==deleteNode){
                    delete[i].next[i] = delete[i].next[i].next[i];
                }
            }
            while(currentLevel>1&&this.head.next[currentLevel-1]==null){
                currentLevel--;
            }
        }
    }

    public int getRandomLevel(){

        int level = 1;
        while(Math.random()<0.5&&level<maxLevel){
            level++;
        }
        return level;
    }

}
